High Efficiency Video Coding (HEVC) is a new coding standard that has been developed in recent years. In the High Efficiency Video Coding (HEVC) system, the fixed-size macroblock of H.264/AVC is replaced by a flexible block, named coding unit (CU). Pixels in the CU share the same coding parameters to improve coding efficiency. A CU may begin with a largest CU (LCU), which is also referred as coded tree unit (CTU) in HEVC. In addition to the concept of coding unit, the concept of prediction unit (PU) is also introduced in HEVC. Once the splitting of CU hierarchical tree is done, each leaf CU is further split into one or more prediction units (PUs) according to prediction type and PU partition.
Along with the High Efficiency Video Coding (HEVC) standard development, the development of extensions of HEVC has also started. The HEVC extensions include screen content coding (SCC). Due to specific characteristics of screen contents, coding tools have been developed and demonstrate significant gains in coding efficiency. Among them, the color index coding (a.k.a. major color based coding) techniques represent block of pixels using indices to the palette (major colors), and encode the palette and the indices by exploiting spatial redundancy. While the total number of possible color combinations is huge, the number of colors in an area of picture is usually very limited for typical screen contents. Therefore, the color index coding becomes very effective for screen content materials. Related key color index coding techniques are briefly reviewed as follows.
Major-Color-Based Screen Content Coding
The major-color-based screen content coding is disclosed in JCTVC-00108 (Guo, et al., “RCE4: Test1. Major-color-based screen content coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 16th Meeting: San Jose, Calif., USA, Jan. 9-17, 2014, Document: JCTVC-P0108). Major-color-based screen content coding is performed on a CU basis. The encoding process is as follows:
Selecting Major Colors
A very simple but efficient histogram based algorithm is used to classify the pixels. In specific, the most significant L peak values in the histogram are selected as major colors, and the pixel values that are close to a major color will be quantized to the major color. Other pixels which do not belong to any major color sets are escape pixels, which will also be quantized before coding. For lossless coding, both of the quantization processes are not used. For each pixel, a color index is assigned to indicate which color set it belongs to. The color index may also be referred as an index for convenience when the term will not cause any confusion. If L major colors are used, the values of major colors 0 to (L−1) are signaled for the set of L major colors and the value of major color N is signaled for the escape pixel set.
Encoding the Color Index
After classification, the pixels of a block can be converted into color indices according to the major color set selected. A predictive coding method is applied to the indices, where a pixel line can be predicted by three different modes, including horizontal mode, vertical mode and normal mode.
Horizontal Mode
In horizontal mode, all the pixels in the same line have the same value. If the value is the same as the first pixel of the above pixel line, only line mode signaling bits are transmitted. Otherwise, the index value is also transmitted.
Vertical Mode
In vertical mode, the current pixel line is the same with the above pixel line. Therefore, only line mode signaling bits are transmitted.
Normal Mode
In normal mode, pixels in a line are predicted individually. For each pixel, the left or above neighbor is used as a predictor, and the prediction symbol is transmitted to the decoder.
Palette Mode Coding
A palette-based coding technique is disclosed in JCTVC-P0198 (Guo et. al., “RCE4: Results of Test 2 on Palette Mode for Screen Content Coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 16th Meeting: San Jose, Calif., USA, Jan. 9-17, 2014, Document: JCTVC-P0198). The palette-based coding is performed on a CU basis. The encoding process is as follows:
Transmission of the Palette:
the palette size is first transmitted followed by the palette elements. The maximum palette size is set to 24.
Transmission of Pixel Values:
the pixels in the CU are encoded in a raster scan order. For each position, a flag is first transmitted to indicate whether the “run mode” or “copy-above mode” is being used.
“Run mode”: In “run mode”, a palette index is first signaled followed by “palette_run” (e.g., M). No further information needs to be transmitted for the current position and the following M positions as they have the same palette index as signaled. The palette index (e.g., i) is shared by all three color components, which means that the reconstructed pixel values are (Y, U, V)=(paletteY[i], paletteU[i], paletteV[i]) if the color space corresponds to YUV.
“Copy-above mode”: In “copy-above mode”, a value “copy_run” (e.g., N) is transmitted to indicate that for the following N positions (including the current one), the palette index is equal to the palette index of the one that is at the same location in the row above.
Transmission of Residue:
The palette indices transmitted are converted back to pixel values and used as the prediction. Residue information is transmitted using HEVC residue coding and is added to the prediction for the reconstruction.
Copy from Previous Row Above
Another index coding mode, called “copy from previous row”, is disclosed in JCTVC-R0202 (Zou et al., “Non-SCCE3: Copy from previous row mode for palette coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, Japan, Jun. 30-Jul. 9, 2014, Document: JCTVC-R0202). This method enables to copy pixels from previously coded rows beyond the row above in the current CU. To achieve a better coding efficiency, all the previous coded rows are available as reference according to JCTVC-R0202. Accordingly, this mode is called “copy from previous row”. This mode is added in the available palette mode candidate list. The row index information is coded when the current string chooses “copy from previous row” mode. The row index is coded using truncated binary codeword. Basically, a shorter codeword is designed for the row which is near to the current row. Like with other modes, the matching length is coded in the bitstream.
FIG. 1 illustrates an example of “copy from previous row” for a current CU consisting of 8×8 pixels. The “copy from previous row” is indicated by an arrow pointing from the current starting pixel to the reference starting pixel. The pixels starting from the current starting pixel can be copied from corresponding reference pixels starting from the reference starting pixel. To reduce the encoder complexity, the “copy from previous row” mode is enabled only when the palette size is larger than 2 for the current CU, and “copy from above” is invalid. To reduce the redundancy with “copy from above”, the reference rows exclude the above row, and therefore, the “copy from previous row” mode is valid starting from the third row of the current CU.
Index Redundancy Removal
In the color index coding, index redundancy may occur under certain conditions. For example, when the current pixel is predicted by the run-mode and the index value needs to be signaled, it implies that the index of the current pixel (also referred to as the current index) is not the same as the most recent coded previous index in the scanning order. FIG. 2A illustrates a scenario of redundancy in the run-mode, where the line-pattern-filled block indicates a current pixel. The run-mode terminates at the pixel before the current pixel. Since the previous color index is “2”, the current index cannot be “2”. Otherwise, the current pixel would have been coded by the run-mode along with the preceding pixels. FIG. 2B illustrates a scenario where redundancy may occur in copy-above mode. In this case, the copy-above mode is terminated at the current pixel. If the copy-above mode had continued to include the current pixel, the current pixel index would be the same as the copy-above predictor (i.e., index “4” above the current pixel). Since the copy-above is terminated at the current pixel, the current pixel index cannot be “4”. This redundancy can be taken into consideration for coding the current pixel by eliminating the redundant index to reduce the number of indices to be coded by one. The decoder would reconstruct the actual index correctly by take into account of the redundancy.
Entropy Coding for ‘Number of Run’
In the current practice, the ‘number of run’ is binarized and coded as follows:                If ‘number of run’ is less than 3, it is unary coded with a maximum number of 3 bits and each bin is context based coded.        If ‘number of run’ is larger than and equal to 3, “111” is context coded and then ‘number of run-3’ is coded as follows with COEF_REMAIN_BIN_REDUCTION and rParam.                    a. When ‘number of run-3’ is smaller than cMax, the quotient of ‘number of run-3’ divided by 2rParam is unary binarized and the remainder is rParam-bit fixed binarized. Both binarized codes are bypass coded. The parameter cMax determined according to cMax=COEF_REMAIN_BIN_REDUCTION×2rParam).            b. When ‘number of run-3’ is greater than or equal to cMax, if ‘number of run-3-cMax’ is greater than or equal to 2rParam+l and less than 2rParam+l+1, COEF_REMAIN_BIN_REDUCTION+l is unary binarized and number of run-3-cMax-2rParam+l is (rParam+l)bit fixed binarized.            Both codes are bypass coded.                        
Table 1 illustrates an example of ‘number of run’-3 binarization table for the case of COEF_REMAIN_BIN_REDUCTION=3 and rParam=3, where “x” in the table can be 0 or 1.
TABLE 1number of run’-3binarizationmin_valuemax_valueprefixsuffix070xxx81510xxx1623110xxx24311110xxx324711110xxxx4879111110xxxxx801431111110xxxxxx14427111111110xxxxxxx272527111111110xxxxxxxx52810391111111110xxxxxxxxx1040206311111111110xxxxxxxxxx20644111111111111110xxxxxxxxxxx
It is desirable to improve the coding efficiency associated with color index map coding including various copy modes.